package org.example.sort;

import java.util.Arrays;

public class order_by_merging {
    public static void main(String[] args) {
        //归并排序
        int[] arr = {5, 2, 4, 6, 1, 3, 8, 7, 9, 0};
        sort(arr);
        System.out.println(Arrays.toString(arr));

    }

    public static void sort(int[] arr) {
        //分开
        separate(arr, 0, arr.length - 1);
    }

    public static void separate(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        separate(arr, left, mid);
        separate(arr, mid + 1, right);
        //合并
        merge(arr, left, mid, right);
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] larr = Arrays.copyOfRange(arr, left, mid + 1);
        int[] rarr = Arrays.copyOfRange(arr, mid + 1, right + 1);

        int l = 0, r = 0, index = left;

        while (index <= right) {
            if (l < larr.length && r < rarr.length && larr[l] <= rarr[r]) {
                arr[index] = larr[l];
                l++;
            } else if (l < larr.length && r < rarr.length && larr[l] > rarr[r]) {
                arr[index] = rarr[r];
                r++;
            } else if (l >= larr.length && r < rarr.length) {
                arr[index] = rarr[r];
                r++;
            } else if (l < larr.length && r >= rarr.length) {
                arr[index] = larr[l];
                l++;
            }
            index++;
        }

    }
}
